package com.wrial.kind.hot;
/*
 * @Author  Wrial
 * @Date Created in 18:09 2020/8/12
 * @Description 汉诺塔问题  A B C 三个柱子  把A->C
                (1) 每次只能移动一个盘子;
                (2) 盘子只能从柱子顶端滑出移到下一根柱子;
                (3) 盘子只能叠在比它大的盘子上。
 */

import java.util.List;

public class Hanota {

    /**
     * 如果1个盘子，那就直接A->C
     * 如果两个盘子，那就借助C将A上面的盘子移到B上，然后将A最底下的盘子移动到C，然后再把B上的盘子移动到C
     * 三个盘子也是如此
     */
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
    }

    private void move(int n, List<Integer> a, List<Integer> b, List<Integer> c) {
        if (n == 1) {
            c.add(a.remove(a.size()-1));
        } else {
            move(n - 1, a, c, b);
            c.add(a.remove(a.size()-1));
            move(n - 1, b, a, c);
        }
    }
}
